//给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。 
//
// 每个正方形的数据square包含3个数值，正方形的左下顶点坐标[X,Y] = [square[0],square[1]]，以及正方形的边长square[2
//]。所求直线穿过两个正方形会形成4个交点，请返回4个交点形成线段的两端点坐标（两个端点即为4个交点中距离最远的2个点，这2个点所连成的线段一定会穿过另外2个交点
//）。2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2}，要求若X1 != X2，需保证X1 < X2，否则需保证Y1 <= Y2。
// 
//
// 若同时有多条直线满足要求，则选择斜率最大的一条计算并返回（与Y轴平行的直线视为斜率无穷大）。 
//
// 示例： 
//
// 输入：
//square1 = {-1, -1, 2}
//square2 = {0, -1, 2}
//输出： {-1,0,2,0}
//解释： 直线 y = 0 能将两个正方形同时分为等面积的两部分，返回的两线段端点为[-1,0]和[2,0]
// 
//
// 提示： 
//
// 
// square.length == 3 
// square[2] > 0 
// 
//
// Related Topics 几何 数学 👍 22 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-08 19:32:39
 * @description 面试题 16.13.平分正方形
 */
public class BisectSquaresLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 BisectSquaresLcci fun=new BisectSquaresLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

		 // 经过中点的就是这条直线
	/*
	* x=x1+t(x2-x1)
	* y=y1+t(y2-y1)
	* */
		 public double[] cutSquares(int[] square1, int[] square2) {
			 //第一个正方形的中心点，x,y坐标及正方形边长
			 double x1 = square1[0] + square1[2]/2.0;
			 double y1 = square1[1] + square1[2]/2.0;
			 int d1 = square1[2];
			 //第二个正方形的中心点，x,y坐标及正方形边长
			 double x2 = square2[0] + square2[2]/2.0;
			 double y2 = square2[1] + square2[2]/2.0;
			 int d2 = square2[2];
			 //结果集
			 double[] res = new double[4];
			 //两个中心坐标在同一条x轴上，此时两条直线的斜率都是无穷大
			 if(x1 == x2){
				 res[0] = x1;
				 res[1] = Math.min(square1[1], square2[1]);
				 res[2] = x1;
				 res[3] = Math.max(square1[1] + d1, square2[1] + d2);
			 }else{
				 //斜率存在，则计算斜率和系数，y = kx + b;
				 double k = (y1 - y2)/(x1 - x2);//斜率计算公式
				 double b = y1 - k*x1;
				 //斜率绝对值大于1，说明与正方形的上边和下边相交
				 if(Math.abs(k) > 1){
					 //先计算底边，也就是两个正方形左下坐标y的最小值
					 res[1] = Math.min(square1[1],square2[1]);
					 res[0] = (res[1] - b)/k;
					 //再计算顶边，也就是两个正方形左下坐标y+边长的最大值
					 res[3] = Math.max(square1[1] + d1,square2[1] + d2);
					 res[2] = (res[3] - b)/k;
				 }else{
					 //斜率绝对值小于等于1，说明与正方形的左边和右边相交，同理
					 res[0] = Math.min(square1[0],square2[0]);
					 res[1] = res[0]*k + b;
					 res[2] = Math.max(square1[0] + d1,square2[0] + d2);
					 res[3] = res[2]*k + b;
				 }
			 }
			 //题目要求x1 < x2,如果结果不满足，我们交换两个点的坐标即可
			 if(res[0] > res[2]){
				 swap(res, 0 ,2);
				 swap(res, 1, 3);
			 }
			 return res;
		 }
	public void swap(double[] res, int x, int y){
		double temp = res[x];
		res[x] = res[y];
		res[y] = temp;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
